package bintree.map_set.LeetCode;
//692. 前K个高频单词
import java.util.*;

/**
 * 思路：先自定义一个类，里面保存key和vale。创建一个Map里面传入就是自定义类的类型。
 * 遇到重复的就把vale表示频次 ++。然后再创建一个最小堆的优先级队列。比较大小就用vale比较。
 *  最后创建List保存优先级队列里面的元素。
 */
//没完成
public class Num692_topKFrequent {
    public static List<String> topKFrequent(String[] words, int k) {
        //1. 扫描原数组里面的字符串录入Map集合中
        Map<String, Integer> map = new HashMap<>();
        for(String i : words){
            if(!map.containsKey(i)){
                //说明此事的 i 在map中不存在
                map.put(i,1);
            }else{
                //说明已经存在了，就增加它的频次
                map.put(i, (map.get(i)) + 1);
            }
        }
        //2.创建优先级队列，因为找最大值，所以用最小堆。
        Queue<Freq> queue = new PriorityQueue<>();
        //扫描Map集合，录入到队列里 //注释：Map.Entry相当于map元素的类型，相当于int【】里面是int
        for(Map.Entry<String, Integer> i : map.entrySet()){
            //注释：Map里面元素是键值对，跟队列保存的Freq类型不一样
            //所以直接offer(i),而是要new一个对象录入
                if(queue.size() < k){
                    queue.offer(new Freq(i.getKey(), i.getValue()));
                }else{
                    Freq freq = queue.peek();//查看堆顶元素
                    if(freq.value <= i.getValue() && i.getKey().compareTo(freq.key) > 0  ){
                        queue.poll();
                        queue.offer(new Freq(i.getKey(), i.getValue()));
                    }else if(freq.value == i.getValue() ){
                        queue.poll();
                        queue.offer(new Freq(i.getKey(), i.getValue()));
                    }

                }
        }//循环结束队里里面就保存了k个最大元素
        //用List集合保存
        List<String> list = new ArrayList<>();
        while(!queue.isEmpty()){
            list.add(queue.poll().key);
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] str = new String[]{"i","love","leetcode","i","love","coding"};
        System.out.println(topKFrequent(str, 3));
    }

}

class Freq implements Comparable<Freq>{

    String key; //数组中出现的元素
    int value;//对应的频次

    @Override //覆写比较大小的规则
    public int compareTo(Freq o) {
        return this.value - o.value;
    }

    //构造方法

    public Freq(String key, int value) {
        this.key = key;
        this.value = value;
    }
}